package greedyAlgorithm;

import org.junit.Test;

/**
 * @author kunkun
 * @className LeetCode_45
 * @Description ...
 * @date 2025/3/18 9:41
 */
public class LeetCode_45 {

    public int jump(int[] nums) {
//        return solution_1(nums);
        return solution_2(nums);
    }

    /**
    * @Description: 贪心策略1：从后往前，逐个求最优解
    * @Author: kunkun
    * @Date:  2025/3/18 10:02
    * @Parameters:
    * @Return
    * @Throws
    */
    private int solution_1(int[] nums) {
        int[] res = new int[nums.length];

        for (int i = nums.length-2; i >=0 ; i--) {
            if (i+nums[i]>=nums.length-1){  //能到就是1
                res[i]=1;
            }else {     //不能到，从后面能到的部分取最小加1，如果都不能到则-1
                int min = Integer.MAX_VALUE;
                if (nums[i]==0){
                    min = -1;
                }else{
                    Boolean flag = true;
                    for (int j = 1; j <= nums[i]; j++) {
                        if (res[i+j]==-1){
                            continue;
                        }
                        if (res[i+j]<min){
                            min=res[i+j];
                            flag = false;
                        }
                    }
                    if (flag){
                        min = -1;
                    }else{
                        min= min+1;
                    }
                }
                res[i] = min;
            }
        }


        return res[0];
    }

    /**
     * @Description: 贪心策略2：从前往后，跳到可跳范围内，不断更新覆盖范围
     * @Author: kunkun
     * @Date:  2025/3/18 10:02
     * @Parameters:
     * @Return
     * @Throws
     */
    private int solution_2(int[] nums) {
        if (nums.length==1){
            return 0;
        }
        int count = 1,rightLimit = nums[0],index = 1;
        while (rightLimit<nums.length-1) {
            int maxLimit =-1;
            for (int i = index; i <= rightLimit; i++) {
                if (i+nums[i]>maxLimit){
                    maxLimit = i+nums[i];
                }
            }
            index = rightLimit+1;
            rightLimit = maxLimit;
            count++;
        }
        return count;
    }
    

    @Test
    public void test(){
        System.out.println(jump(new int[]{5,9,3,2,1,0,2,3,3,1,0,0}));
    }


}
